package java学习.leetcode.editor.cn;

import java.util.ArrayList;

/**
 * @author 刘世锦
 * 2023-01-15 13:51:05	 当前时间
 */
//给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。 
//
// 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入: head = [-10,-3,0,5,9]
//输出: [0,-3,9,-10,null,5]
//解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。
// 
//
// 示例 2: 
//
// 
//输入: head = []
//输出: []
// 
//
// 
//
// 提示: 
//
// 
// head 中的节点数在[0, 2 * 104] 范围内 
// -105 <= Node.val <= 105 
// 
// Related Topics 树 二叉搜索树 链表 分治 二叉树 
// 👍 794 👎 0

public class 有序链表转换二叉搜索树{
	public static void main(String[] args) {
		Solution solution = new 有序链表转换二叉搜索树().new Solution();
		
	}
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
	/**
	 * 使用快慢指针找出mid节点 （mid = slow）
	 *      s
	 *          f
	 *  1 2 3 4 5 6
	 */
	public TreeNode sortedListToBST(ListNode head) {
		if (head==null) return null;
		if (head.next==null) return new TreeNode(head.val);
		ListNode fast = head,slow = head;
		ListNode pre = null;
		while (fast!=null&&fast.next!=null){
			fast = fast.next.next;
			pre = slow; // 记录 mid 前一个节点
			slow = slow.next;
		}
		TreeNode node = new TreeNode(slow.val);
		// 0,mid-1 分支=左子树
		pre.next = null;
		node.left = sortedListToBST(head);
		// mid+1,ListNodeLength-1 右子树
		node.right = sortedListToBST(slow.next);
		return node;
	}

		/**
         * 思想的懒惰
         */
	public TreeNode sortedListToBST1(ListNode head) {
		ArrayList<Integer> list = new ArrayList<>();
		if (head==null) return null;
		while (head!=null){
			list.add(head.val);
			head = head.next;
		}
		return  dfs(list,0,list.size()-1);
	}

	private TreeNode dfs( ArrayList<Integer> list, int left, int right) {
		if (left>right){
			return null;
		}
		int mid = left+(right-left)/2;
		TreeNode node = new TreeNode(list.get(mid));
		node.left = dfs(list,left,mid-1);
		node.right = dfs(list,mid+1,right);
		return node;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
